package com.leecode.xiehf.page_10;

import com.leecode.Printer;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
 *
 * 注意：n 的值小于15000。
 *
 * 示例1:
 *
 * 输入: [1, 2, 3, 4]
 *
 * 输出: False
 *
 * 解释: 序列中不存在132模式的子序列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/132-pattern
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0456 extends Printer {

    public static void main(String[] args) {
        Solution_0456 solution = new Solution_0456();

        System.out.println(solution.find132pattern(new int[]{1, 2 ,3 ,4}));
    }

    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if(n<3){
            return false;
        }
        int[] stack = new int[n];
        int idx = -1;
        stack[++idx] = nums[n-1];
        int maxK = Integer.MIN_VALUE;
        for(int i = n-2;i>=0;i--){
            if(nums[i]<maxK){
                return true;
            }
            while(idx!=-1&&stack[idx]<nums[i]){
                maxK = stack[idx--];
            }
            stack[++idx] = nums[i];
        }
        return false;
    }
}
